package 每日一题;

/**
 * @author 会玩的洋洋
 * https://leetcode.cn/problems/binary-tree-coloring-game/
 */
public class _1145_二叉树着色游戏 {
    /**
        记录x所在位置
     */
    TreeNode xNode;

    /**
     * 利用判断三个位置，一个是x的左子树，一个是x的右子树，一个是其他节点，若存在大于(n + 1) / 2的位置，则玩家二获胜，反之失败
     * 执行用时：0ms，内存消耗：39.3MB
     * @param root
     * @param n
     * @param x
     * @return
     */
    public boolean btreeGameWinningMove(TreeNode root, int n, int x) {
        find(root, x);

        int leftSize = getSubtreeSize(xNode.left);
        if (leftSize >= (n + 1) >> 1) {
            return true;
        }

        int rightSize = getSubtreeSize(xNode.right);
        if (rightSize >= (n + 1) >> 1) {
            return true;
        }

        int otherSize = n - leftSize - rightSize - 1;
        return otherSize >= (n+ 1) >> 1;
    }

    /**
     * 查找x所在位置，并赋值给xNode
     * @param node
     * @param x
     */
    public void find(TreeNode node, int x) {
        if (xNode != null || node == null) {
            return;
        }
        if (node.val == x) {
            xNode = node;
            return;
        }
        find(node.left, x);
        find(node.right, x);
    }

    /**
     * 计算该节点下的节点总数
     * @param node
     */
    public int getSubtreeSize(TreeNode node) {
        if (node == null) {
            return 0;
        }
        return getSubtreeSize(node.left) + getSubtreeSize(node.right) + 1;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
